It is known that the Internet is divided into tens of thousands of Autonomous Systems. Each Autonomous System (AS) is an independently administrated domain. The routing information within an AS is maintained by Interior Gateway Protocols (IGPs), while the Border Gateway Protocol (BGP) is employed to maintain and exchange inter-domain routing information among the various Autonomous Systems (ASs).
Stability of inter-domain routing is of critical importance to maintain the connectivity and reliability of data communications systems such as the Internet. However, since inter-domain exchange of traffic is between different administrative domains, the process of routing is highly dependent on the local rules of these domains. Fortunately, not all route changes can cause instability.
Examples of events that do result in anomalous route changes are infrastructure failures (e.g., due to disasters like hurricanes or earthquakes), power outages (e.g., large scale events like the blackout in Northeastern United States in August 2003), worm attacks and BGP router misconfigurations. Such anomalous route changes and the impact of local rules on these route changes can be observed by monitoring the BGP update messages seen at the peering points. However, monitoring BGP updates is a challenging task since there are multiple prefixes that need to be monitored.
There has been recent work focusing on the detection of routing anomalies using BGP update message data. In J. Wu et al., “Finding a Needle in a Haystack: Pinpointing Significant BGP Routing Changes in an IP Network,” Proceedings of Networked Systems Design and Implementation, Boston, Mass., May 2005, a system is proposed that can be used for online generation of routing disruption reports. However, the system focuses on identifying events that originate close to the observation point and thus may not be effective in detecting wide-spread instabilities far from their observation point.
A learning-based approach described in J. Zhang et al., “Learning-Based Anomaly Detection in BGP Updates,” Proceedings of the 2005 ACM MineNet Workshop, pp. 219-220, Philadelphia, Pa., August 2005, proposes the use of wavelet transformations to determine patterns of BGP update-dynamics, which translates the problem into the wavelet domain. However, there is a loss of time granularity as a result of requiring sufficient sample support for accurate estimation of the wavelet basis.
The methods disclosed in S. T. Teoh et al., “Visual-based Anomaly Detection for BGP Origin Change Events,” Proceedings of the 14th IFIP/IEEE Workshop on Distributed Systems: Operations and Management, pp. 155-168, Heidelberg, Germany, October 2003, and S. T. Teoh et al., “Combining Visual and Automated Data Mining for Near-Real-Time Anomaly Detection and Analysis in BGP,” Proceedings of CCS Workshop on Visualization and Data Mining for Computer Security, ACM Conference on Computer and Communications Security, pp. 35-44, Washington, D.C., October 2004, utilize visual-based techniques for the detection and location of the instabilities. In such approaches, data mining techniques are used to render the data free of noise and translate the data into graphical views for easier identification by a human operator.
Nonetheless, improved techniques for detecting instability events in data communications systems that support inter-domain routing are needed.